package com.sx.sx1.lintcode.day919;
import java.util.*;
public class LC860 {

    static class Solution {
        /**
         * @param grid: a list of lists of integers
         * @return: return an integer, denote the number of distinct islands
         */
        public int numberofDistinctIslands(int[][] grid) {
            int n = grid.length;
            int m = grid[0].length;
            Set<String> set = new HashSet<>();

            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <m ; j++) {
                    StringBuilder t =new StringBuilder();
                    if(grid[i][j] ==1){
                        dfs(grid,i,j,i,j,t);
                        set.add(t.toString());
                    }
                }
            }
            return set.size();
        }

        public void dfs(int[][] grid,int i,int j,int baasx,int basey,StringBuilder t){
            int n = grid.length;
            int m = grid[0].length;
            if(i<0 || i==n || j<0||j ==m || grid[i][j] ==0)
                return;

            grid[i][j] =0;
            t.append((i-baasx)+"_"+ (j-basey));
            dfs(grid,i-1,j,baasx,basey,t);
            dfs(grid,i+1,j,baasx,basey,t);
            dfs(grid,i,j-1,baasx,basey,t);
            dfs(grid,i,j+1,baasx,basey,t);
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        int[][] arr1 =   {
                {1,1,0,0,1},
                {1,0,0,0,0},
                {1,1,0,0,1},
                {0,1,0,1,1}
        };

        int[][] arr2 =  {
                {1,1,0,0,0},
                {1,1,0,0,0},
                {0,0,0,1,1},
                {0,0,0,1,1}
        };

        System.out.println(obj.numberofDistinctIslands(arr1)); //3
        System.out.println(obj.numberofDistinctIslands(arr2)); //2
    }



    static class Solutionold {
        /**
         * @param grid: a list of lists of integers
         * @return: return an integer, denote the number of distinct islands
         */
        public int numberofDistinctIslands(int[][] grid) {
            // write your code here
            return fun(grid);
        }

        public int fun(int[][] arr){
            if(arr == null || arr.length == 0|| arr[0].length == 0) return 0;

            Set<String> ans = new HashSet<>();
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    Set<String> tmp = new HashSet<>();
                    if(arr[i][j] ==1){
                        process(arr,i,j,i,j,tmp);
                        ans.add(tmp.toString());
                    }
                }
            }
            return ans.size();
        }

        public void process(int[][] arr,int i,int j,int basex,int basey,Set<String> s){
            if(i< 0 || i== arr.length || j< 0  || j== arr[0].length || arr[i][j] ==0)
                return;

            arr[i][j] =0;
            s.add((i-basex)+"_"+(j-basey));

            process(arr, i-1, j, basex, basey, s);
            process(arr, i+1, j, basex, basey, s);
            process(arr, i, j-1, basex, basey, s);
            process(arr, i, j+1, basex, basey, s);
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有196条未读消息，请及时查看
860 · 不同岛屿的个数
算法
中等
通过率
52%

题目
题解45
笔记
讨论95
排名
记录
描述
给定一个由0和1组成的非空的二维网格，一个岛屿是指四个方向（包括横向和纵向）都相连的一组1（1表示陆地）。你可以假设网格的四个边缘都被水包围。

找出所有不同的岛屿的个数。如果一个岛屿与另一个岛屿形状相同（不考虑旋转和翻折），我们认为这两个岛屿是相同的。

注意：

11
1
和

 1
11
是不同的岛屿，因为我们不考虑旋转和翻折。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


网格的每一个维度的长度都不超过50。

样例
样例 1:

输入:
  [
    [1,1,0,0,1],
    [1,0,0,0,0],
    [1,1,0,0,1],
    [0,1,0,1,1]
  ]
输出: 3
解释:
  11   1    1
  1        11
  11
   1
样例 2:

输入:
  [
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
  ]
输出: 1
标签
企业
Amazon
相关题目

433
岛屿的个数
简单

434
岛屿的个数II
中等

804
不同岛屿的数量II
困难
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
